/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package grasp;

import java.io.* ;
import java.util.*;

/**
 *
 * @author walter
 */
public class Algoritmo {
    ArrayList<Ciudad> arCity ;
    ArrayList<Vuelo> arVuelos ;
    ArrayList<Ciudad> ruta ;
    double P[] ;
    
    ArrayList<Integer> getVecinos( Ciudad city ){
        ArrayList<Integer> v = new ArrayList<Integer>() ;
        for(int i = 0 ; i < arVuelos.size() ; i++) {
            Vuelo vuelo = arVuelos.get( i ) ;
            if( vuelo.origen.diff( city ) == false ){
                v.add( i ) ;
            }
        }
        return v ;
    }
    
    public int getOpcion( ArrayList<Integer> vuelos , int tiempoRest ){
        // LOGICA DE ELECCION ... EN BASE A LA PROBABILIDAD
//        int P[] = new int[ vuelos.size() ] ;
//        
//        for(int i = 0 ; i < vuelos.size() ; i++){
////            P[ i ] = generateProb();
//            P[ i ] = prob.nextInt() ;
//        }
        
        for(int i = 0 ; i < vuelos.size() ; i++){
            for(int j = i+1 ; j < vuelos.size() ; j++){
                if( P[ i ] > P[ j ] ){
                    int aux = vuelos.get( i ) ;
                    vuelos.set( i , vuelos.get( j ) ) ;
                    vuelos.set( j , aux ) ;
                }
            }
        }
        
        boolean enc = false ;
        int idx = -1 ;
        for(int i = 0 ; i < vuelos.size() && enc == false ; i++){
            Vuelo v = arVuelos.get( vuelos.get( i ) ) ;
            if( ruta.contains( v.destino ) == true ){ continue ; }
            if( v.duracion > tiempoRest ){ continue ; }
            if( v.capVuelo == 0 ){ continue ; }
            enc = true ;
            idx = i ;
        }
        if( idx < 0 ) {
            return idx ;
        }
        return vuelos.get( idx ) ;
    }
    
    public int getRangoHora( int serv ){
        serv = 3 ;
        int resp ;
        switch( serv ){
            case 0: resp = 8 ; break ;
            case 1: resp = 16 ; break ;
            case 2: resp = 24 ; break ;
            default: resp = 48 ; break ;
        }
        return resp ;
    }
    
    public double generateProb(){
        Random r = new Random() ;
//        System.out.println( "Random = " + r.nextDouble() ) ;
        return r.nextDouble() ;
    }
    
    public void init(){
        P = new double[ arVuelos.size() ] ;
        Random prob = new Random() ;
        for(int i = 0 ; i < arVuelos.size() ; i++){
            P[ i ] = prob.nextDouble() ;
        }
    }
    
    public ArrayList<Integer> read() throws FileNotFoundException{
        Scanner sc = new Scanner( new File( "input.in" ) ) ;
        
        arCity = new ArrayList<Ciudad>() ;
        int n = sc.nextInt() ;
        for(int i = 0 ; i < n ; i++){
            int x = sc.nextInt() ;
            int y = sc.nextInt() ;
            int cap = sc.nextInt() ;
            arCity.add( new Ciudad( i , x , y , cap ) ) ;
        }
        
        arVuelos = new ArrayList<Vuelo>() ;
        int m = sc.nextInt() ;
        for(int i = 0 ; i < m ; i++){
            int ini = sc.nextInt() ;
            int fin = sc.nextInt() ;
            int cap = sc.nextInt() ;
            int dur = sc.nextInt() ;
            double costo = sc.nextDouble() ;
            arVuelos.add( new Vuelo( arCity.get( ini ) , arCity.get( fin ) , cap , dur , costo ) ) ;
//            arVuelos.get( i ).write() ;
        }
        
        ArrayList<Integer> R = new ArrayList<Integer>() ;
        R.add( sc.nextInt() ) ;
        R.add( sc.nextInt() ) ;
        
        init() ;
        return R ;
    }
    
    public void ocuparAlmacen( int id ){
        // LUEGO CONECCION CON BD ... ACTUALIZAR LA CAPACIDAD DEL ALMACEN
        arVuelos.get( id ).capVuelo-- ;
//        Vuelo v = arVuelos.get( id ) ;
//        v.capVuelo-- ;
//        arVuelos.set( id , v ) ;
    }
    
    public ArrayList<Double> start( Ciudad origen , Ciudad destino , int tipoServicio ){
        int tmax = getRangoHora( tipoServicio ) ;
        
        ruta = new ArrayList<Ciudad>() ;
        ruta.add( origen ) ;
        
        Ciudad actual = origen ;
        int tFinal = 0 ;
        double dist = 0.0 ;
        double costFinal = 0.0 ;
        
        int cont = 0 ;
        
        while( destino.diff( actual ) == true ){
            ArrayList<Integer> vecinos = getVecinos( actual ) ;
            int pos = getOpcion( vecinos , tmax ) ;
            
            if( pos == -1 ) { // Caso que no se pueda seguir yendo por aqui
                if( ruta.size() > 1 ){ // Se regresa un nodo
                    ruta.remove( ruta.size() - 1 ) ;
                    actual = ruta.get( ruta.size() - 1 ) ;
                    cont = 0 ;
                    continue ;
                }else if( ruta.size() == 1 && cont < 10000 ){ // Se intenta ver otra ruta
                    cont++ ;
                    continue ;
                }
                return new ArrayList<Double>() ; // No se encontro ruta
            }
            Vuelo v = arVuelos.get( pos ) ;
            
            actual = v.destino ;
            tmax -= v.duracion ;
            tFinal += v.duracion ;
            dist += v.getDist() ;
            costFinal += v.costo ;
            ruta.add( actual ) ;
        }
        
        for(int i = 0 ; i < ruta.size() ; i++) {
            ocuparAlmacen( ruta.get( i ).id ) ;
        }
        
        
        ArrayList<Double> resp = new ArrayList<Double>() ;
        resp.add( Double.parseDouble( tFinal + "" ) ) ;
        resp.add( costFinal ) ;
        resp.add( dist ) ;
        
        return resp ;
    }
    
    public void print( ArrayList<Double> data ) throws IOException{
        FileWriter fw = new FileWriter( "output.in" ) ;
        PrintWriter pw = new PrintWriter( fw ) ;
        
        if( data.isEmpty() ){
            pw.println( "No se encontró ruta" ) ;
        }
        
        String t[] = new String[ 4 ] ;
        t[ 0 ] = "Tiempo total " ;
        t[ 1 ] = "Costo total " ;
        t[ 2 ] = "Distancia total " ;
        
        for(int i = 0 ; i < data.size() ; i++){
            pw.println( t[ i ] + "= " + data.get( i ) ) ;
        }
        pw.close() ;
    }
}
